'''
最大的能被7整除子序列的和
'''

def f(nums, k = 7):
    n = len(nums)
    dp = [[0] * k for _ in range(n + 1)]    # dp[i][j]：表示数组前i个元素的子序列，累加和%k == j，的最大累加和
    # dp[0][0] = 0
    # 第一维度依赖前面的，第二维度乱依赖
    for i in range(1, n + 1):
        for yu in range(k):
            r1 = dp[i-1][yu]    # 不要当前的数
            # y1当前余数，y2想要的余数=yu ，y3需要之前凑够的余数
            # y1, y2 = nums[i] % k, yu
            # y3 = (k + y2 - y1) % k
            # r2 = nums[i] + dp[i-1][y3]  # 要当前的数
            r2 = nums[i] + dp[i-1][(k + yu - nums[i] % k) % k]  # 要当前的数
            dp[i][yu] = max(r1, r2)
    return dp[n][0]
